package com.base.leetcode;

import com.base.dataStructure.Tree.TreeNode;

import java.util.Arrays;

/**
 * @Author: hdhao
 * @Create: 2023/4/5 - 20:57
 * @Version: v1.0
 */
//根据中序与后序遍历结果构造二叉树
public class Leetcode106 {
    /*
        左根右
        inOrder = {4,2,1,6,3,7}
        左右根
        postOrder = {4,2,6,7,3,1}
     */
    public TreeNode buildTree(int[] inOrder, int[] postOrder) {
        if (inOrder.length == 0 || postOrder.length == 0) {
            return null;
        }
        //根节点
        int rootValue = postOrder[postOrder.length - 1];
        TreeNode root = new TreeNode(rootValue);
        //切分左右子树
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootValue) {
//                inOrder = {4,2,1,6,3,7}
                int[] inLeft = Arrays.copyOfRange(inOrder, 0, i);
                int[] inRight = Arrays.copyOfRange(inOrder, i+1, inOrder.length);
//                postOrder = {4,2,6,7,3,1}
                int[] postLeft = Arrays.copyOfRange(postOrder, 0, i);
                int[] postRight = Arrays.copyOfRange(postOrder, i, postLeft.length - 1);

                root.left = buildTree(inLeft, postLeft);
                root.right = buildTree(inRight, postRight);
                break;
            }
        }
        return root;
    }
}
